Maximum-Cup 2018 C - 嘘つきな天使たち

提出

code: python

n = int(input())

graph = [[] for _ in range(n)]

for idx, g in enumerate(a):

g -= 1

# 頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse

def dfs(v,color):

# 今いる点を着色

return False

return False

# 調べ終わったら矛盾がないのでTrue

return True

# 2部グラフならTrue, そうでなければFalse

def is_bipartite():

return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

print(n//2) if is_bipartite() else print(-1)

解答

code: python

from collections import defaultdict

n = int(input())

d = defaultdict(list)

# 天使に隣接しているのは悪魔、悪魔に隣接しているのは天使になる

for idx, v in enumerate(a):

def dfs(v, color):

# 塗った時の数を記録

return False

return False

return True

ans = 0

count = defaultdict(int)

for i in range(1, n+1):

if not dfs(i, 1): # 二部グラフではない

print(-1)

exit()

print(max(count.values()))

テーマ

メモ

提出

code: python

from collections import defaultdict

n = int(input())

d = defaultdict(list)

for idx, v in enumerate(a):

# print(d)

# 閉路